package secondary

/*
	输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

	假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

	示例 1:
	Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
	Output: [3,9,20,null,null,15,7]
	示例 2:

	Input: preorder = [-1], inorder = [-1]
	Output: [-1]
	限制：

	0 <= 节点个数 <= 5000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func BuildTree(preorder []int, inorder []int) *TreeNode {
	return buildTree(preorder, inorder)
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	// 1. 根据题意、前序遍历数组中、第一个元素一定是某个树的根节点
	if len(preorder) == 0 || len(inorder) == 0 {
		return nil
	}
	rootVal := preorder[0]
	// 2. 找到root在inorder中的位置
	i := 0
	for ; i < len(inorder); i++ {
		if rootVal == inorder[i] {
			break
		}
	}
	// 3. 根据i对preorder和inorder进行分解
	root := &TreeNode{
		Val: rootVal,
	}
	root.Left = buildTree(preorder[1:i+1],inorder[:i])
	root.Right = buildTree(preorder[i+1:], inorder[i+1:])
	return root
}
